This invention relates to the use of programmable integrated circuit devices (e.g., field-programmable gate arrays or other programmable logic devices (PLDs)) to perform matrix multiplication operations.
In a multiplication of two input matrices AA and BB to form resultant matrix CC, each resultant element cij in the resultant matrix CC will be the dot product of the ith row in matrix AA and the jth column in matrix BB. For example, c57 will be the dot product of the fifth row of matrix AA and the seventh column of matrix BB. The length of a row of (i.e., the number of columns, k, in) matrix AA is equal to the height of a column of (i.e., the number of rows in) matrix BB. As is evident, the computation of each element cij requires k multiplications. Moreover, there are i×j elements cij in matrix CC, for a total of i×j×k multiplications. For large matrices (with, e.g., hundreds of elements per dimension), there may not be enough multipliers and logic resources available on a programmable integrated circuit device, such as an FPGA, to perform even the k multiplications to multiply just one row and column together for a single resultant element cij. k−1 adders also are required to add the individual products to obtain the dot product.